#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;

/*HJJ QQ479287006
 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

 

示例 1：


输入：head = [1,2,2,1]
输出：true
示例 2：


输入：head = [1,2]
输出：false

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*
 TODO 并不是已下子写出来的 需要翻转后半部分我写成前半部分了
 * */
ListNode *reverseNode(ListNode *&head) {
    if (!head || head->next == nullptr)
        return head;

    ListNode *ret = reverseNode(head->next);

    head->next->next = head;
    head->next = nullptr;

    return ret;

}


bool isPalindrome(ListNode *head) {

    if (!head || head->next == nullptr)
        return true;

    ListNode *fast = head;
    ListNode *slow = head;


    while (fast && fast->next && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    //slow is mid
    ListNode *start = slow->next;

    slow->next = nullptr;

    //1 0 0
    ListNode *re = reverseNode(start);//一定要翻转后半部分因为前半部分 如果是奇数数据会多一个导致不皮皮
    while (re) {
        if (re->val == head->val) {
            re = re->next;
            head = head->next;
        } else {
            return false;
        }

    }


    return true;
}